package com.arithmeticEveryDay.leetCode;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution78 {
    
    int n;
    int[] nums;
    List<List<Integer>> res;
    List<Integer> path;
    
    
    private Solution78(int n, int[] nums) {
        super();
        this.n = n;
        this.nums = nums;
        res = new ArrayList<List<Integer>>();
        path = new ArrayList<Integer>();
    }

    
    public List<List<Integer>> subsets(int[] nums) {
        // 空集合也算是一个子集
        res.add(new ArrayList<>());
        dfs(nums,0);
        return res;
    }

    public void dfs(int[] nums,int startIndex) {
        // System.out.println(startIndex + ", " + path);
        for (int i = startIndex; i < nums.length; i++) {
            // 每遍历一个元素，就将该元素加入到path中，并加入到 res集合中。都算是一个子集
            path.add(nums[i]);
            res.add(new ArrayList<Integer>(path));
            dfs(nums,i+1);
            path.remove(path.size() - 1);
        }
    }
    

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        Solution78 s = new Solution78(n, nums);
        s.subsets(nums);
        System.out.println(s.res);
    }

}
